入门

题目 入门

思路分析

一条路走到黑

确定一下以后写这类问题的规范

x正方向为下 y正方向为右

dx[4]={-1,0,1,0};

dy[4]={0,1,0,-1};

代码实现

#include<bits/stdc++.h>
using namespace std;

const int N=30;
char g[N][N];
int n,m;
int res;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool st[N][N];

void dfs(int x,int y){
	for(int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(nx<0 || nx>=n || ny<0 || ny>=m)
			continue;
		if(g[nx][ny]!='.')
			continue;
		if(st[nx][ny])
			continue;
		st[nx][ny]=true;
		res++;
		dfs(nx,ny);
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>m>>n;
	for(int i=0;i<n;i++){
		cin>>g[i];
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(g[i][j]=='@'){
				st[i][j]=true;
				res++;
				dfs(i,j);
			}
		}
	}
	cout<<res;
	return 0;
 }

#include<bits/stdc++.h>
using namespace std;

const int N=30;
char g[N][N];
int n,m;
int res;
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
bool st[N][N];

bool isVaild(int x,int y){
	return x>=0 && x<=n-1 && y>=0 && y<=m-1 && !st[x][y];
}

void dfs(int x,int y){
	for(int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(isVaild(nx,ny) && g[nx][ny]=='.'){
			st[nx][ny]=true;
			res++;
			dfs(nx,ny);
            //该点只能走一次 不能回溯
		}
	}
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>m>>n;
	for(int i=0;i<n;i++){
		cin>>g[i];
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(g[i][j]=='@'){
				st[i][j]=true;
				res++;
				dfs(i,j);
			}
		}
	}
	cout<<res;
	return 0;
 }

同类题型

视频讲解

⬅️ 4、方格分割 🏠 00-刷题理模型 ➡️ 简单图